03 Sifra

Crveni astronaut ima zadatak da unese tačnu šifru kako drugi astronauti ne bi saznali da je zapravo vanzemaljac. Šifra je dužine n i sastoji se iz cifara 1, 2 i 4. Crveni je saznao neke delove šifre, kao i da šifra sadrži tačno k jedinica i da predstavlja broj deljiv sa 3. Napisati program koji pomaže Crvenom da ispiše sve šife koje ispunjavaju date uslove u leksikografskom poretku pre nego što drugi astronauti posumnjaju da je on uljez među njima. Vremenska složenost mora biti O(2^m) gde je m broj nepoznatih cifara u šifri, dok prostorna složenost mora biti O(n).

Ulaz

Sa standardnog ulaza se unosi broj k (1 ≤ k ≤ n). Nakon toga se unosi niska dužine n (1 ≤ n ≤ 20) koja se sastoji iz karaktera 0, 1, 2 i 4 koja određuje koja cifra se nalazi na kojoj poziciji u šifri (tamo gde je 0 nije poznata cifra).

Izlaz

Na standardni izlaz ispisati sve tražene šifre uređene leksikografski rastuće, svaku u zasebnom redu.

Primer

Ulaz

3
10240220102

Izlaz

11242222122
11244224142
12241222122
12242221122
12242222112
14241224142
14244221142
14244224112